class Solution {
public:
    //外观数列——模拟+双指针
    string countAndSay(int n) 
    {
        string ret("1");
        int count = 0;
        for(int i = 1; i < n; i++)//翻译n-1次即可
        {   
            string tmp;//用于存放翻译的结果
            int len = ret.size();
            for(int left = 0, right = 0;right < len;)
            {
                while(right < len && ret[left] == ret[right]) //统计相同数字的个数
                    right++;
                //翻译
                tmp += to_string(right - left);
                tmp += ret[left];
                left = right; // 向后继续遍历
            }
            ret = tmp;        
        }
        return ret;
    }
};

//数青蛙
class Solution {
public:
    int minNumberOfFrogs(string croakOfFrogs) 
    {
        unordered_map<char,int> countMap;
        string tmp = "croak";
        for(auto ch : tmp)
        {
            countMap[ch] = 0;
        }

        for(int i = 0; i <croakOfFrogs.size();i++)
        {
            if(croakOfFrogs[i] == 'c')
            {
                if(countMap['k'])//判断是否有已经叫完的
                    countMap['k']--;

                countMap['c']++;
            }
            else
            {
                //找一下前驱避免无效字符串
                if(croakOfFrogs[i] == 'r')
                {
                    if(countMap['c'] == 0)
                        return -1;
                    else
                    {
                        countMap['c']--;
                        countMap['r']++;
                    }
                }
                else if(croakOfFrogs[i] == 'o')
                {
                    if(countMap['r'] == 0)
                        return -1;
                    else
                    {
                        countMap['r']--;
                        countMap['o']++;
                    }
                }
                else if(croakOfFrogs[i] == 'a')
                {
                    if(countMap['o'] == 0)
                        return -1;
                    else
                    {
                        countMap['o']--;
                        countMap['a']++;
                    }
                }
                else if(croakOfFrogs[i] == 'k')
                {
                    if(countMap['a'] == 0)
                        return -1;
                    else
                    {
                        countMap['a']--;
                        countMap['k']++;
                    }
                }
            }
        }
        
        //判断是否都叫完了
        for(int i = 0; i < 4; i++)
        {
            if(countMap['c'] != 0)
                return -1;
            else if(countMap['r'] != 0)
                return -1;
            else if(countMap['o'] != 0)
                return -1;
            else if(countMap['a'] != 0)
                return -1;
        }

        return countMap['k'];
    }
};

//优化版本数青蛙
class Solution {
public:
    int minNumberOfFrogs(string croakOfFrogs) 
    {
        string tmp = "croak";
        int n = tmp.size();
        vector<int> hash(n);//用数组模拟哈希表

        unordered_map<char,int> index;//[ch,ch的下标]
        //初始化index
        for(int i = 0; i < n; ++i)
        {
            index[tmp[i]] = i;
        }

        for(auto ch : croakOfFrogs)
        {
            if(ch == 'c')
            {
                if(hash[n - 1])
                    hash[n-1]--;
                hash[0]++;
            }
            else
            {
                if(hash[index[ch] - 1] == 0)
                    return -1;
                else
                {
                    hash[index[ch] - 1]--;
                    hash[index[ch]]++;
                }
            }
        }

        for(int i = 0; i < n - 1;i++)
        {
            if(hash[i] != 0)
                return -1;
        }

        return hash[n - 1];

    }
};